package com.datastructures2.sort;

/**
 * @author MaoLin Wang
 * @date 2020/2/1814:35
 */
public class InsertSort{
    public static <T extends Comparable<? super T>> void insertSort(T [] arr){
        int j;
        for (int i = 1; i < arr.length; i++) {
            T temp=arr[i];

            for ( j = i; j >0&&temp.compareTo(arr[j-1])<0 ; j--) {
                arr[j]=arr[j-1];
            }
            arr[j]=temp;
        }

    }


    /**
     * 插入排序
     * @param arr
     * @param <T>
     */
    public static <T extends Comparable<? super T>> void insertSort(T [] arr,int left,int right){
        int j;
        for (int i = left; i <= right; i++) {
            T temp=arr[i];

            for ( j = i; j >left&&temp.compareTo(arr[j-1])<0 ; j--) {
                arr[j]=arr[j-1];
            }
            arr[j]=temp;
        }
    }
    public static void main(String[] args) {
        Integer [] arr={2,44,1,2,6,4};
        insertSort(arr);
        for(Integer i:arr){
            System.out.println(i);
        }
    }
}
